1. Field of the Invention
This invention relates to a method and apparatus for optimizing a real-value function in Boolean domain.
2. Background Art
The design of a circuit involves both identifying circuit components necessary to accomplish one or more functions and determining a physical arrangement of the identified circuit components. It is generally desirable to find an optimal circuit design which minimizes the size and cost of the circuit and maximizes the speed and efficiency of the circuit.
Optimization of the circuit components which are to comprise a circuit is generally accomplished in the Boolean domain. Circuit components for generating the desired circuit function are represented by one or more Boolean operators, such as AND/XOR etc., with each operator or combination of operators representing an electronic xe2x80x9cgatexe2x80x9d or component. Once the components of a desired circuit have been represented with the appropriate Boolean operators, it is possible to optimize the circuit using the known laws of Boolean algebra.
Application of these laws may permit the various Boolean operators representing the circuit to be reconfigured, such as by lessening the total number of operators (and hence circuit components) needed to create the desired circuit. The various operators of the optimized Boolean operator set are then converted back into corresponding real circuit components, i.e. transistors, diodes, etc.
Once the circuit components are known, the layout of these components is performed in the real domain (i.e. non-Boolean domain). The various components may be mapped into Cartesian coordinates and moved about until their arrangement is optimized. For example, the optimum arrangement of the components may be that where they occupy the least space or have the shortest interconnect distances.
A significant problem associated with this method of circuit design is that the circuit component determination and component layout portions of the design phase are performed independently. As a result, optimal circuit design conditions which are achieved in one portion of the design phase may be unusable in a later portion of the design phase. As an example of this problem, the optimal choice of circuit components might differ if it were possible to consider the layout or arrangement of the components at the same time as the possible combinations of the components.
A source of this problem is that the two portions of the design phase are performed independently, the circuit component portion of the design phase being performed in the Boolean domain and the layout portion performed in the real domain.
It would be advantageous if the two portions of the design phase, i.e. that in the Boolean and real domains, could be merged. It would be advantageous if the domains could be merged and optimization in both domains realized when optimization in the Boolean domain is accomplished.
The invention is a method and apparatus for optimizing a real function in the Boolean domain.
In accordance with one embodiment of the method, the real function is represented as a Boolean function. A binary decision diagram for the Boolean function is created, the binary decision diagram having a root and at least one variable node. The number of vertices for at least one variable node of the binary decision diagram is determined.
The function is optimized by selecting a path leading from the root to a variable node of the binary decision diagram having the least number of associated vertices. The solution values of one or more variables of the Boolean function are determined in accordance with the path(s) through the binary decision diagram. These values comprise an optimized solution set for the real function.
In one or more embodiments, the method may be utilized to determine the shortest xe2x80x9cinterconnectxe2x80x9d path between two or more points. In this arrangement, the Boolean function represents one or more segments of an interconnect having end-points at the points to be connected. Solution values for the connecting points of the segment of the interconnect are yielded from the path through the binary decision diagram.
In one or more embodiments, computer hardware and/or software is arranged to perform the method of the invention.
Further objects, features and advantages of the invention will become apparent from the detailed description of the drawings which follows, when considered with the attached figures.